package demo1;

import javax.swing.tree.TreeCellRenderer;

public class ResearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    TreeNode root;
    private static void createTree() {
        TreeNode A = new TreeNode(50);
        TreeNode B = new TreeNode(20);
        TreeNode C = new TreeNode(70);
        TreeNode D = new TreeNode(10);
        TreeNode E = new TreeNode(30);
        TreeNode F = new TreeNode(60);
        TreeNode G = new TreeNode(80);
        TreeNode H = new TreeNode(40);
        A.left = B;
        A.right = C;
        B.right = E;
        B.left = D;
        C.left = F;
        C.right = G;
        E.right = H;
    }
    public TreeNode search(int key) {
        if(root == null){
            return null;
        }
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val == key) {
                return cur;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return null;
    }
    public boolean insert(int val) {
        if(root == null) {
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null) {
            if(cur.val == val) {
                return false;
            }else if(cur.val > val) {
                prev = cur;
                cur = cur.left;
            }else {
                prev = cur;
                cur = cur.right;
            }
        }
        TreeNode newTree = new TreeNode(val);
        if(prev.val > val) {
            prev.left = newTree;
        }else {
            prev.right = newTree;
        }
        return true;
    }
    //删除指定节点
    public void remove(int val) {
        if(root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        if(cur.val > val) {
            parent = cur;
            cur = cur.left;
        }else if(cur.val < val) {
            parent = cur;
            cur = cur.right;
        }else {
            parent = cur;
            removeNode(cur,parent);//通过上述代码找到要删除的节点，再通过removeNode(cur,parent)方法删除节点
        }
    }
    //删除节点的方法
    private void removeNode(TreeNode cur, TreeNode parent) {
        //1、cur.left == null：要删除的节点只有右节点
        if(cur.left == null) {
            if(cur == root) { //1.1、cur为root，则root = cur.right
                root = cur.right;//要删除的为根节点，根节点往后移
            }else {
                if(cur == parent.right) {//1.2、cur不为root，cur为父亲节点(parent)的右结点
                    parent.right = cur.right;//让parent的右节点指向cur的右节点，跳过cur
                }else {//1.3、cur不为root，cur为父亲节点(parent)的左结点
                    parent.left = cur.right;//让parent的左节点指向cur的右节点，跳过cur
                }
            }
        }else if(cur.right == null) {//2、cur.right == null
            if(cur == root) { //2.1、cur为root，则root = cur.left
                root = cur.left;//要删除的为根节点，根节点往后移
            }else {
                if(cur == parent.right) {//2.2、cur不为root，cur为父亲节点(parent)的右结点
                    parent.right = cur.left;//让parent的右节点指向cur的左节点，跳过cur
                }else {//2.3、cur不为root，cur为父亲节点(parent)的左结点
                    parent.left = cur.left;//让parent的左节点指向cur的左节点，跳过cur
                }
            }
        }else {//3、cur.left != null && cur.right != null
            //这里的删除相当于替换删除。在以cur为root的树中，在右树找到最左边的节点（或者在左树找到最右边的节点）
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while (target.left != null) {
                //在右树找到最左边的节点target
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            //target在targetParent的左右子树位置不一样，删除方式不一样
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }


    public static void main(String[] args) {
        createTree();
    }
}
